package MinimumHeightTrees;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        int[] begin=new int[edges.length*2+2];
        int[] end=new int[edges.length*2+2];
        int[] point=new int[edges.length*2+2];
        int[] start=new int[n];
        int[] outer=new int[n];
        if (n==2){
        	List<Integer> result=new ArrayList<Integer>();
        	result.add(0);
        	result.add(1);
        	return result;
        }
        int count=0;
        for (int i=0;i<edges.length;i++){
        	count++;
        	add(edges[i][0],edges[i][1],begin,end,point,start,count);
        	outer[edges[i][1]]++;
        	count++;
        	add(edges[i][1],edges[i][0],begin,end,point,start,count);
        	outer[edges[i][0]]++;
        }
        int ans=Integer.MAX_VALUE;
        List<Integer> result=new ArrayList<Integer>();
        Queue<Integer> queue=new LinkedList<Integer>();
        int[] high=new int[n];
        boolean[] bo=new boolean[n];
        for (int i=0;i<n;i++){
        	if (outer[i]==1) { queue.offer(i); bo[i]=true; outer[i]=0; high[i]=1;}
        }
        int now=0;
        while (queue.isEmpty()==false){
        	now=queue.poll();
        	int next=start[now];
        	while (next!=0){
        		int to=end[next];
        		outer[to]--;
        		if (outer[to]==1 && bo[to]==false) {queue.add(to); bo[to]=true; outer[to]=0; high[to]=high[now]+1;}
        		next=point[next];
        	}
        }
        int max=0;
        for (int i=0;i<n;i++) 
        		if (high[i]>max){
        			result.clear();
        			result.add(i);
        			max=high[i];
        		}
        		else if (high[i]==max)
        			result.add(i);
        return result;
        
    }

	private void add(int i, int j, int[] begin, int[] end, int[] point, int[] start, int count) {
		begin[count]=i;
		end[count]=j;
		point[count]=start[i];
		start[i]=count;
	}
	
	
	public static void main(String args[]){
		int n=8;
		int[][] edges={{1, 0},{1, 2},{2, 3},{0, 4},{4, 6},{6, 7},{4, 5}};
		Solution so=new Solution();
		so.findMinHeightTrees(n, edges);
	}
}
